/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
// dfs(回溯) 暴力 超时
var combinationSum4 = function (nums, target) {
	let res = 0
	const dfs = (comb, sum) => {
		if (sum >= target) {
			if (sum === target) {
				res++
			}
			return
		}
		for (let i = 0; i < nums.length; i++) {
			comb.push(nums[i])
			dfs(comb, sum + nums[i])
			comb.pop()
		}
	}
	dfs([], 0)
	return res
}
// 记忆化搜索
var combinationSum4 = (nums, target) => {
	const memo = new Map() // 目标 target 对应多少种方案
	const dfs = (target) => {
		if (target === 0) return 1 // 说明找到一种方案
		if (memo.has(target)) return memo.get(target)
		let res = 0
		for (const num of nums) {
			if (num > target) continue
			res += dfs(target - num)
		}
		memo.set(target, res)
		return res
	}
	return dfs(target)
}
// 动态规划
var combinationSum4 = (nums, target) => {
	// dp[i] 表示选取元素和为 i 的方案数
	const dp = new Array(target + 1).fill(0)
	// 和为0 只有什么都不选 1 种方案
	dp[0] = 1
	for (let i = 1; i <= target; i++) {
		for (const num of nums) {
			if (num <= i) {
				dp[i] += dp[i - num]
			}
		}
	}
	return dp[target]
}
const res = combinationSum4([4, 2, 1], 32)
console.log(res)
